import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-03-26
 * Time: 15:44
 */
public class test_1 {
public static   int minFallingPathSum1(int[][] matrix) {
        // 1. 创建 dp 表
        int n=matrix.length;
        //每层的下降路径
        int[] dp=new int[n];
        // 2. 初始化
        int[] tmp = matrix[0];
        int min =0;
        for (int i = 0; i < tmp.length; i++) {
            if (tmp[min]>tmp[i]){
                min=i;
            }
        }
        System.out.println(min);
        dp[0]=tmp[min];
        // 3. 填表
        for (int i = 1; i < n; i++) {
            if (min==0){
                if (matrix[i][min]>matrix[i][min+1]){
                    min=min+1;
                }
            }else if (min==n-1){
                if (matrix[i][min]>matrix[i][min-1]){
                    min=min-1;
                }
            }else {
                if (matrix[i][min]>matrix[i][min+1]){
                    min=min+1;
                }
                if (matrix[i][min]>matrix[i][min-1]){
                    min=min-1;
                }
            }
            System.out.println(matrix[i][min]);
            dp[i]=dp[i-1]+matrix[i][min];
        }
        // 4. 返回值
        return dp[n-1];
    }
    public  static int minFallingPathSum(int[][] matrix){
        // 1. 创建 dp 表
        int n=matrix.length;
        int[][] dp =new int[n][n];
        // 2. 初始化
        for (int i = 0; i < n; i++) {
            dp[0][i]=matrix[0][i];
        }
        // 3. 填表
        for (int i=1;i<n;i++){
            for (int j = 0; j < n; j++) {
                int min=j;
                if (min==0){
                    if (dp[i-1][min]>dp[i-1][min+1]){
                        min=min+1;
                    }
                }else if (min==n-1){
                    if (dp[i-1][min]>dp[i-1][min-1]){
                        min=min-1;
                    }
                }else {
                    int tmp=min;
                    if (dp[i-1][min+1]<dp[i-1][tmp]){
                        tmp=min+1;
                    }
                    if (dp[i-1][min-1]<dp[i-1][tmp]){
                        tmp=min-1;
                    }
                    min =tmp;
                }
                dp[i][j]=matrix[i][j]+dp[i-1][min];
            }
        }
        // 4. 返回值
        int[] tmp=dp[n-1];
        for (int i = 0; i < n; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        Arrays.sort(tmp);
        return tmp[0];
}

    public static void main(String[] args) {
        int[][] s={{100,-42,-46,-41},{31,97,10,-10},{-58,-51,82,89},{51,81,69,-51}};
        System.out.println(minFallingPathSum(s));
    }
}
